/*
 * @lc app=leetcode.cn id=132 lang=javascript
 *
 * [132] 分割回文串 II
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var minCut = function (s) {
  const size = s.length;
  // 预处理
  // isPal[i][j]是否为回文串，[i,j]区间的字符串
  const isPal = new Array(size).fill(0).map((_) => new Array(size).fill(true));
  for (let i = size - 1; i >= 0; i--) {
    for (let j = i + 1; j < size; j++) {
      isPal[i][j] = s[i] === s[j] && isPal[i + 1][j - 1];
    }
  }

  // 记录当前位置需要分割几次
  const dp = new Array(size).fill(Number.POSITIVE_INFINITY);
  for (let i = 0; i < size; i++) {
    if (isPal[0][i]) {
      dp[i] = 0;
    } else {
      for (let j = 0; j < i; j++) {
        if (isPal[j + 1][i]) {
          dp[i] = Math.min(dp[i], dp[j] + 1);
        }
      }
    }
  }

  return dp[size - 1];
};
// @lc code=end
